"""
343. 整数拆分
https://leetcode.cn/problems/integer-break/
"""
class Solution:
    # O(n^2) O(n)
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n+1)
        dp[1] = 1
        dp[2] = 1
        if n <= 2: return 1

        for i in range(3, n+1):
            curr = 0
            for j in range(1, i-1):
                k = i - j
                curr = max(curr, j*(i-j))    # 不拆
                curr = max(curr, j*dp[i-j])  # 拆分
            dp[i] = curr
        
        return dp[n]
    
    # 尽量拆分成 3
    def integerBreak2(self, n: int) -> int:
        if n <= 3: return n-1

        res = 1
        while n>4:
            res *= 3
            n -= 3
        
        return res*n
